YES 2.9090000000000003 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/FiniteMap.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:



HASKELL
  ↳ CR

mainModule FiniteMap
  ((elemFM :: Int  ->  FiniteMap Int a  ->  Bool) :: Int  ->  FiniteMap Int a  ->  Bool)

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap a b) where 

  elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool
elemFM key fm 
case lookupFM fm key of
  Nothing-> False
  Just elt-> True

  lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a
lookupFM EmptyFM key Nothing
lookupFM (Branch key elt _ fm_l fm_rkey_to_find 
 | key_to_find < key = 
lookupFM fm_l key_to_find
 | key_to_find > key = 
lookupFM fm_r key_to_find
 | otherwise = 
Just elt


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Case Reductions:
The following Case expression
case lookupFM fm key of
 Nothing → False
 Just elt → True

is transformed to
elemFM0 Nothing = False
elemFM0 (Just elt) = True



↳ HASKELL
  ↳ CR
HASKELL
      ↳ BR

mainModule FiniteMap
  ((elemFM :: Int  ->  FiniteMap Int a  ->  Bool) :: Int  ->  FiniteMap Int a  ->  Bool)

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap a b) where 

  elemFM :: Ord a => a  ->  FiniteMap a b  ->  Bool
elemFM key fm elemFM0 (lookupFM fm key)

  
elemFM0 Nothing False
elemFM0 (Just eltTrue

  lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b
lookupFM EmptyFM key Nothing
lookupFM (Branch key elt _ fm_l fm_rkey_to_find 
 | key_to_find < key = 
lookupFM fm_l key_to_find
 | key_to_find > key = 
lookupFM fm_r key_to_find
 | otherwise = 
Just elt


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
HASKELL
          ↳ COR

mainModule FiniteMap
  ((elemFM :: Int  ->  FiniteMap Int a  ->  Bool) :: Int  ->  FiniteMap Int a  ->  Bool)

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap a b) where 

  elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool
elemFM key fm elemFM0 (lookupFM fm key)

  
elemFM0 Nothing False
elemFM0 (Just eltTrue

  lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b
lookupFM EmptyFM key Nothing
lookupFM (Branch key elt vw fm_l fm_rkey_to_find 
 | key_to_find < key = 
lookupFM fm_l key_to_find
 | key_to_find > key = 
lookupFM fm_r key_to_find
 | otherwise = 
Just elt


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Cond Reductions:
The following Function with conditions
lookupFM EmptyFM key = Nothing
lookupFM (Branch key elt vw fm_l fm_rkey_to_find
 | key_to_find < key
 = lookupFM fm_l key_to_find
 | key_to_find > key
 = lookupFM fm_r key_to_find
 | otherwise
 = Just elt

is transformed to
lookupFM EmptyFM key = lookupFM4 EmptyFM key
lookupFM (Branch key elt vw fm_l fm_rkey_to_find = lookupFM3 (Branch key elt vw fm_l fm_rkey_to_find

lookupFM0 key elt vw fm_l fm_r key_to_find True = Just elt

lookupFM2 key elt vw fm_l fm_r key_to_find True = lookupFM fm_l key_to_find
lookupFM2 key elt vw fm_l fm_r key_to_find False = lookupFM1 key elt vw fm_l fm_r key_to_find (key_to_find > key)

lookupFM1 key elt vw fm_l fm_r key_to_find True = lookupFM fm_r key_to_find
lookupFM1 key elt vw fm_l fm_r key_to_find False = lookupFM0 key elt vw fm_l fm_r key_to_find otherwise

lookupFM3 (Branch key elt vw fm_l fm_rkey_to_find = lookupFM2 key elt vw fm_l fm_r key_to_find (key_to_find < key)

lookupFM4 EmptyFM key = Nothing
lookupFM4 wv ww = lookupFM3 wv ww

The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
HASKELL
              ↳ Narrow

mainModule FiniteMap
  (elemFM :: Int  ->  FiniteMap Int a  ->  Bool)

module FiniteMap where
  import qualified Maybe
import qualified Prelude

  data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b


  instance (Eq a, Eq b) => Eq (FiniteMap a b) where 

  elemFM :: Ord b => b  ->  FiniteMap b a  ->  Bool
elemFM key fm elemFM0 (lookupFM fm key)

  
elemFM0 Nothing False
elemFM0 (Just eltTrue

  lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a
lookupFM EmptyFM key lookupFM4 EmptyFM key
lookupFM (Branch key elt vw fm_l fm_rkey_to_find lookupFM3 (Branch key elt vw fm_l fm_r) key_to_find

  
lookupFM0 key elt vw fm_l fm_r key_to_find True Just elt

  
lookupFM1 key elt vw fm_l fm_r key_to_find True lookupFM fm_r key_to_find
lookupFM1 key elt vw fm_l fm_r key_to_find False lookupFM0 key elt vw fm_l fm_r key_to_find otherwise

  
lookupFM2 key elt vw fm_l fm_r key_to_find True lookupFM fm_l key_to_find
lookupFM2 key elt vw fm_l fm_r key_to_find False lookupFM1 key elt vw fm_l fm_r key_to_find (key_to_find > key)

  
lookupFM3 (Branch key elt vw fm_l fm_rkey_to_find lookupFM2 key elt vw fm_l fm_r key_to_find (key_to_find < key)

  
lookupFM4 EmptyFM key Nothing
lookupFM4 wv ww lookupFM3 wv ww


module Maybe where
  import qualified FiniteMap
import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
QDP
                  ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Zero), bb) → new_elemFM01(wx44, Neg(Zero), bb)
new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, Succ(wx1520), Zero, ba) → new_elemFM01(wx150, Pos(Succ(wx151)), ba)
new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM0(wx4000, wx41, wx42, wx43, wx44, wx300, wx300, wx4000, bb)
new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Zero), bb) → new_elemFM01(wx43, Neg(Zero), bb)
new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Zero), bb) → new_elemFM01(wx44, Pos(Zero), bb)
new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, Succ(wx1520), Succ(wx1530), ba) → new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, wx1520, wx1530, ba)
new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM03(wx4000, wx41, wx42, wx43, wx44, wx300, wx4000, wx300, bb)
new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, Succ(wx1610), Zero, bd) → new_elemFM01(wx159, Neg(Succ(wx160)), bd)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Zero, Succ(wx800), bc) → new_elemFM01(wx76, Neg(Succ(wx78)), bc)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx700), Zero, h) → new_elemFM00(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx69), Succ(wx64), h)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx700), Succ(wx710), h) → new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, wx700, wx710, h)
new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, Succ(wx1610), Succ(wx1620), bd) → new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, wx1610, wx1620, bd)
new_elemFM01(Branch(Pos(Zero), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM01(wx44, Pos(Succ(wx300)), bb)
new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Zero), bb) → new_elemFM01(wx43, Pos(Zero), bb)
new_elemFM01(Branch(Neg(wx400), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM01(wx44, Pos(Succ(wx300)), bb)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, bc) → new_elemFM04(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx73), Succ(wx78), bc)
new_elemFM02(wx64, wx65, wx66, wx67, wx68, wx69, h) → new_elemFM00(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx69), Succ(wx64), h)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), bc) → new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, bc)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Zero, Succ(wx710), h) → new_elemFM01(wx67, Pos(Succ(wx69)), h)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Zero, Zero, bc) → new_elemFM05(wx73, wx74, wx75, wx76, wx77, wx78, bc)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Zero, Zero, h) → new_elemFM02(wx64, wx65, wx66, wx67, wx68, wx69, h)
new_elemFM01(Branch(Neg(Zero), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM01(wx43, Neg(Succ(wx300)), bb)
new_elemFM05(wx73, wx74, wx75, wx76, wx77, wx78, bc) → new_elemFM04(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx73), Succ(wx78), bc)
new_elemFM01(Branch(Pos(wx400), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM01(wx43, Neg(Succ(wx300)), bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 4 SCCs.

↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ AND
QDP
                        ↳ QDPSizeChangeProof
                      ↳ QDP
                      ↳ QDP
                      ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Zero, bc) → new_elemFM04(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx73), Succ(wx78), bc)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx790), Succ(wx800), bc) → new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, wx790, wx800, bc)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Zero, Zero, bc) → new_elemFM05(wx73, wx74, wx75, wx76, wx77, wx78, bc)
new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM03(wx4000, wx41, wx42, wx43, wx44, wx300, wx4000, wx300, bb)
new_elemFM01(Branch(Neg(Zero), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM01(wx43, Neg(Succ(wx300)), bb)
new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, Succ(wx1610), Zero, bd) → new_elemFM01(wx159, Neg(Succ(wx160)), bd)
new_elemFM03(wx73, wx74, wx75, wx76, wx77, wx78, Zero, Succ(wx800), bc) → new_elemFM01(wx76, Neg(Succ(wx78)), bc)
new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, Succ(wx1610), Succ(wx1620), bd) → new_elemFM04(wx155, wx156, wx157, wx158, wx159, wx160, wx1610, wx1620, bd)
new_elemFM05(wx73, wx74, wx75, wx76, wx77, wx78, bc) → new_elemFM04(wx73, wx74, wx75, wx76, wx77, wx78, Succ(wx73), Succ(wx78), bc)
new_elemFM01(Branch(Pos(wx400), wx41, wx42, wx43, wx44), Neg(Succ(wx300)), bb) → new_elemFM01(wx43, Neg(Succ(wx300)), bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ AND
                      ↳ QDP
QDP
                        ↳ QDPSizeChangeProof
                      ↳ QDP
                      ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Zero), bb) → new_elemFM01(wx43, Pos(Zero), bb)
new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Zero), bb) → new_elemFM01(wx44, Pos(Zero), bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ AND
                      ↳ QDP
                      ↳ QDP
QDP
                        ↳ QDPSizeChangeProof
                      ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, Succ(wx1520), Zero, ba) → new_elemFM01(wx150, Pos(Succ(wx151)), ba)
new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM0(wx4000, wx41, wx42, wx43, wx44, wx300, wx300, wx4000, bb)
new_elemFM01(Branch(Neg(wx400), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM01(wx44, Pos(Succ(wx300)), bb)
new_elemFM02(wx64, wx65, wx66, wx67, wx68, wx69, h) → new_elemFM00(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx69), Succ(wx64), h)
new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, Succ(wx1520), Succ(wx1530), ba) → new_elemFM00(wx146, wx147, wx148, wx149, wx150, wx151, wx1520, wx1530, ba)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Zero, Succ(wx710), h) → new_elemFM01(wx67, Pos(Succ(wx69)), h)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Zero, Zero, h) → new_elemFM02(wx64, wx65, wx66, wx67, wx68, wx69, h)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx700), Zero, h) → new_elemFM00(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx69), Succ(wx64), h)
new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, Succ(wx700), Succ(wx710), h) → new_elemFM0(wx64, wx65, wx66, wx67, wx68, wx69, wx700, wx710, h)
new_elemFM01(Branch(Pos(Zero), wx41, wx42, wx43, wx44), Pos(Succ(wx300)), bb) → new_elemFM01(wx44, Pos(Succ(wx300)), bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ BR
        ↳ HASKELL
          ↳ COR
            ↳ HASKELL
              ↳ Narrow
                ↳ QDP
                  ↳ DependencyGraphProof
                    ↳ AND
                      ↳ QDP
                      ↳ QDP
                      ↳ QDP
QDP
                        ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_elemFM01(Branch(Neg(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Zero), bb) → new_elemFM01(wx44, Neg(Zero), bb)
new_elemFM01(Branch(Pos(Succ(wx4000)), wx41, wx42, wx43, wx44), Neg(Zero), bb) → new_elemFM01(wx43, Neg(Zero), bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: